package pers.qianyu.month_202012.date_20201213;

import org.junit.*;

/**
 * 64. 最小路径和
 * https://leetcode-cn.com/problems/minimum-path-sum/
 *
 * @author mizzle rain
 * @date 2020-12-13 17:43
 */
public class MinPathSum {
    public int minPathSum(int[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        if (grid[0].length == 0) {
            return 0;
        }
        // dp[i][j] 表示到点 (i, j) 的最小路径
        int[][] dp = new int[grid.length][grid[0].length];
        // 初始化 base case
        dp[0][0] = grid[0][0];
        for (int i = 1; i < dp.length; i++) {
            dp[i][0] = grid[i][0] + dp[i - 1][0];
        }
        for (int i = 1; i < dp[0].length; i++) {
            dp[0][i] = grid[0][i] + dp[0][i - 1];
        }
        //System.out.println(Arrays.deepToString(dp));
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[dp.length - 1][dp[0].length - 1];
    }

    @Test
    public void test1() {
        int[][] grid = {
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        };
        int result = new MinPathSum().minPathSum(grid);
        System.out.println("result = " + result);
    }
}
